// tspcluster - Traveling Salesman Problem
// Copyright (C) 2006  Frederik Carlier
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace UGent.Tsp
{
    /// <summary>
    /// Does a cyclic permutation of k random cities.
    /// </summary>
    [HasParameter(true,2)]
    public class Swap343 : ISwapper
    {
        private const int DefaultCount = 5;

        #region Constructors
        public Swap343(Route route)
            : this(route, DefaultCount)
        {
        }

        public Swap343(Route route, int count)
        {
            this.route = route;
            this.cityCount = route.Map.CityCount;
            this.count = count;
            this.cities = new int[count];
            this.subset = new Subset();
        }
        #endregion

        #region Properties
        // The set of cities to be permuted
        private int[] cities;
        private int this[int index]
        {
            get
            {
                return cities[Cyclic.GetIndex(index, count)];
            }
            set
            {
                cities[Cyclic.GetIndex(index, count)] = value;
            }
        }
        private int cityCount;
        private int proposed;
        private int accepted;
        private Subset subset;

        public int ProposedMoves
        {
            get { return proposed; }
        }

        public int AcceptedMoves
        {
            get { return accepted; }
        }

        private Route route;
        public IRoute Route
        {
            get { return route; }
        }

        private int count;
        public int Count
        {
            get
            {
                return count;
            }
        }
        #endregion

        #region ISwapper Members

        public void Generate()
        {
            // Generate a set of k unique random
            // numbers from a set of N values
            // (eg: get k unique numbers from 0..N-1)
            subset.Random(0, cityCount - 1, count, cities);
            proposed++;
        }

        public void Do()
        {
            // Save the index of the first city
            int temp = route[cities[0]];

            // Shift the second to the last city
            for (int i = 0; i < count - 1; i++)
            {
                route[cities[i]] = route[cities[i + 1]];
            }

            // Write the last city
            route[cities[count - 1]] = temp;

            accepted++;
        }

        public double GetDelta()
        {
            // Get the index of the previous city swapped
            // Get the index of the current city swapped
            // Get the index of the next city swapped

            // If the previous city swapped is the current left neighbour,
            // do nothing. 
            // Else, substract the distance
            // Which city will be the new left neighbour? In theory, the city
            // at route[cities[i-1]-1]. But. If cities[i-2] = cities[i-1]-1
            // this will be route[cities[i-1]] because that city is shifted as
            // well.

            // If the next city swapped is the current right neighbour,
            // do nothing. 
            // Else, substract the distance.

            double delta = 0;

            for (int i = 0; i < count; i++)
            {
                int oldIndex = this[i];
                int oldLeft = Cyclic.GetIndex(oldIndex - 1, cityCount);
                int oldRight = Cyclic.GetIndex(oldIndex + 1, cityCount);
                int newIndex = this[i - 1];
                int newLeft = -1;
                int newRight = -1;

                // Basic question: Did the previous city shift only 1 block?
                bool newLeftHasShifted = (this[i - 2] == Cyclic.GetIndex(this[i - 1] - 1, cityCount));

                if (newLeftHasShifted)
                {
                    // If so, the new left city is the city that was 
                    // the previously shifted city.
                    newLeft = this[i - 1];
                }
                else
                {
                    // If not, it is the city at the left of the new location.
                    newLeft = Cyclic.GetIndex(this[i - 1] - 1, cityCount);
                }

                // Basic question: did this city shift only 1 block?
                bool newRightHasShifted = (Cyclic.GetIndex(oldIndex, cityCount) == Cyclic.GetIndex(newIndex + 1, cityCount));

                if (newRightHasShifted)
                {
                    // If so, the new right is simply the old right.
                    newRight = this[i + 1];
                }
                else
                {
                    // If not, the new right is the city right of the
                    // new location.
                    newRight = Cyclic.GetIndex(newIndex + 1, cityCount);
                }

                //Debug.WriteLine(String.Format("City with index {0} had the old configuration {1}-{0}-{2}, and has the new configuration {3}-{0}-{4}", oldIndex, oldLeft, oldRight, newLeft, newRight));

                delta -= Route.GetDistance(oldLeft, oldIndex);
                //Debug.WriteLine(string.Format("-d({0},{1})", oldLeft, oldIndex));

                delta += Route.GetDistance(newLeft, oldIndex);
                //Debug.WriteLine(string.Format("+d({0},{1})", newLeft, oldIndex));

                if (!newRightHasShifted)
                {
                    delta += Route.GetDistance(oldIndex, newRight);
                    //Debug.WriteLine(string.Format("+d({0},{1})", oldIndex, newRight));
                }

                bool oldRightHasShifted = Cyclic.GetIndex(this[i] + 1, cityCount) == this[i + 1];
                if (!oldRightHasShifted)
                {
                    delta -= Route.GetDistance(oldIndex, oldRight);
                    //Debug.WriteLine(string.Format("-d({0},{1})", oldIndex, oldRight));
                }
            }

            //Debug.WriteLine(string.Empty);
            return delta;
        }

        #endregion
    }
}
